import sys

class Solution(object):
    def calculateMinimumHP(self, dungeon):
        """
        :type dungeon: List[List[int]]
        :rtype: int
        """
        for row in dungeon:
            row.reverse()
        dungeon.reverse()

        R = len(dungeon)
        C = len(dungeon[0])
        dp = [[0 for _ in range(C)] for _ in range(R)]
        for length in range(0, R+C-1):
            for r in range(0, length+1):
                c = length-r
                if 0<=r<R and 0<=c<C:
                    if r==0 and c==0:
                        dp[r][c] = 1 if dungeon[r][c]>=0 else -dungeon[r][c]+1
                    else:
                        case0 = dp[r][c-1] if c-1>=0 else sys.maxsize
                        case1 = dp[r-1][c] if r-1>=0 else sys.maxsize
                        dp[r][c] = dungeon[r][c] - min(case0, case1)
                        dp[r][c] = 1 if dp[r][c]>=0 else -dp[r][c]
        return dp[-1][-1]
